\documentclass[a4paper,12pt]{article}
\usepackage{fullpage}
\usepackage[british]{babel}
\usepackage[latin1]{inputenc}

\usepackage[boxed]{algorithm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm} \newtheorem{theorem}{Theorem}
\usepackage{color}
\usepackage{clrscode3e}
\usepackage{float}
\usepackage{graphicx}
\usepackage{grffile} % allows spaces in filenames
\usepackage{rotating}
\usepackage{tikz} \usetikzlibrary{trees}
\usepackage{hyperref} % should always be the last package
\hypersetup{colorlinks=true,urlcolor=blue}

% useful colours (use sparingly!):
\newcommand{\blue}[1]{{\color{blue}#1}}
\newcommand{\green}[1]{{\color{green}#1}}
\newcommand{\red}[1]{{\color{red}#1}}

% useful (wrappers for) math symbols:
\newcommand{\Cardinality}[1]{\left\lvert#1\right\rvert}
%\newcommand{\Cardinality}[1]{\##1}
\newcommand{\Implies}{\Rightarrow}
\newcommand{\Inter}{\cap}
\newcommand{\Tuple}[1]{\langle#1\rangle}
%\newcommand{\Tuple}[1]{[#1]}
\newcommand{\Union}{\cup}

% coding convention of AD2 (additions to clrscode3e):
\newcommand{\CounterExample}[1]{\li \Comment \textbf{Counterexample:} #1}
\newcommand{\Example}[1]{\li \Comment \textbf{Example:} #1}
\newcommand{\LoopInvariant}[1]{\Comment \textbf{Invariant:} #1}
\newcommand{\None}{(none)}
\newcommand{\Post}[1]{\li \Comment \textbf{Post:} #1}
\newcommand{\Pre}[1]{\li \Comment \textbf{Pre:} #1}
\newcommand{\ReprConvention}[1]{\Comment \textbf{Representation Convention:} #1}
\newcommand{\ReprInvariant}[1]{\Comment \textbf{Representation Invariant:} #1}
\newcommand{\Signature}[1]{\li \Comment \textbf{Signature:} #1}
\newcommand{\Variant}[1]{\Comment \textbf{Variant:} #1}

% type system:
\newcommand{\Array}[2]{\mathbf{~array}[#1 \twodots #2]}
\newcommand{\Char}{\textbf{char}}
\newcommand{\Int}{\textbf{int}}
\newcommand{\Boolean}{\textbf{boolean}}
\newcommand{\Real}{\textbf{real}}
\newcommand{\String}{\textbf{string}}

\title{Algorithms and Data Structures II \\
    Course 1DL230 at Uppsala University \\
    Spring Semester 2011 \\
    Report for Assignment $2$} % replace n by 1, 2, or 3

\author{Rodrigo GUMUCIO \and Wei HU} % replace by your name(s)

%\date{Month Day, Year}
\date{\today}

\begin{document}

\maketitle

\section{Search Term Replacement}
\label{sect:STR}

\subsection{Algorithm}
\label{sect:algo:str}

\begin{algorithm} % make it float to the top of a page
\begin{codebox}
\label{algo:str1}
\Procname{$\proc{STR}(u,r,\rho,i,j)$}
\Signature{$(\Char \Array{1}{i}~u, \Char \Array{1}{j}~r$,\\
\quad $\Int \Array{1}{a+1}[1..a+1]~\rho,\Int~i, \Int~j) \to \Int~s[i,j]$}
\Pre{$u$ and $r$ represent two sets of char wihich belong to the alphabet \\
\quad including dash(-), $\rho$ represents a matrix of the measures of \\
\quad resemblance of pairs of letters,whose size is $(a+1)\times(a+1)$}
\Post{$s[i,j]$ return the minimum difference of two strings $u[1..i]$ and $r[1..j]$} \\
\Variant {$m,n$, $m$ is the length of $u$,$n$ is the length of $r$}
\li Let $s[1..m,1..n]$ be a new int array
\li \If $i == 0 \mbox{ and } j == 0$\Do 
\li 	$s[i,j] \gets \rho[$-,-$]$;
\li 	\Return $s[i,j]$; \End
\li \If $i == 0 \mbox{ and } j \neq 0$ \Do
\li 	\If $s[i,j-1]$ is null \Do 
\li 		$s[i,j-1] \gets STR(u,r,\rho,i,j-1)$; \End
\li 	$s[i,j] \gets s[i,j-1] + \rho[$-,$r[j]]$; 
\li 	\Return $s[i,j]$;\End
\li \If $i \neq 0 \mbox{ and } j == 0$ \Do
\li 	\If $s[i-1,j]$ is null \Do 
\li 		$s[i-1,j] \gets STR(u,r,\rho,i-1,j)$; \End
\li 	$s[i,j] \gets s[i-1,j] + \rho[u[i]$,-$]$; 
\li 	\Return $s[i,j]$;\End
\li \If $s[i-1,j]$ is null \Do\
\li 	$(s[i-1,j],u1,r1,\ell) \gets STR(u,r,u1,r1,\ell,\rho,i-1,j)$; \End
\li \If $s[i,j-1]$ is null \Do\
\li 	$(s[i,j-1],u1,r1,\ell) \gets STR(u,r,u1,r1,\ell,\rho,i,j-1)$; \End
\li \If $s[i-1,j-1]$ is null \Do\
\li 	$(s[i-1,j-1],u1,r1,\ell) \gets STR(u,r,u1,r1,\ell,\rho,i-1,j-1)$;\End
\li $s[i,j] \gets \min\{(s[i-1,j]+\rho[u[i],$-$])$,\\
	$(s[i,j-1]+\rho[$-$,r[j]]),(s[i-1,j-1]+\rho[u[i],r[j]])\}$;
\li \Return $s[i,j]$;
\end{codebox}
\caption{Search Term Replacement algorithm}
\end{algorithm}

\begin{algorithm} % make it float to the top of a page
\begin{codebox}
\label{algo:str2}
\Procname{$\proc{STR}(u,r,u1,r1,\ell,\rho,i,j)$}
\Signature{$(\Char \Array{1}{i}~u, \Char \Array{1}{j}~r,\Char \Array{1}{i}~u1,$\\
\quad  $\Char \Array{1}{j}~r1, \Int~\ell,\Int \Array{1}{a+1}[1..a+1]~\rho,\Int~i, \Int~j)$\\
\quad  $\to \Int~s[i,j]$}
\Pre{$u$ and $r$ represent two sets of char wihich belong to the alphabet \\
\quad including dash(-), $\rho$ represents a matrix of the measures of \\
\quad resemblance of pairs of letters,whose size is $(a+1)\times(a+1)$}
\Post{$s[i,j]$ returns the minimus difference of two strings $u[1..i]$ and $r[1..j]$,\\
\quad $u1$ and $r1$ return the positionning of $u$ and $r$,$\ell$ returns the length of $u1$ and $r1$} \\
\Variant {$m,n$, $m$ is the length of $u$,$n$ is the length of $r$}
\li Let $s[1..m,1..n]$ be a new int array
\li \If $i == 0 \mbox{ and } j == 0$\Do 
\li 	$s[i,j] \gets \rho[$-,-$]$;
\li 	\Return $(s[i,j],u1,r1,\ell)$; \End
\li \If $i == 0 \mbox{ and } j \neq 0$ \Do
\li 	\If $s[i,j-1]$ is null \Do 
\li 		$(s[i,j-1],u1,r1,\ell) \gets STR(u,r,u1,r1,\ell,\rho,i,j-1)$; \End
\li 	$\ell = \ell + 1$;
\li 	$u1[\ell] = $ -; 
\li 	$r1[\ell] = r[j]$;
\li 	$(s[i,j],u1,r1,\ell) \gets s[i,j-1] + \rho[$-,$r[j]]$;
\li 	\Return $(s[i,j],u1,r1,\ell)$; \End
\li \If $i \neq 0 \mbox{ and } j == 0$ \Do
\li 	\If $s[i-1,j]$ is null \Do 
\li 		$(s[i-1,j],u1,r1,\ell) \gets STR(u,r,u1,r1,\ell,\rho,i-1,j)$; \End
\li 		$\ell = \ell + 1$;
\li 		$u1[\ell] = u[i]$; 
\li 		$r1[\ell] = $ -; 
\li 		$s[i,j] \gets s[i-1,j] + \rho[u[i]$,-$]$;
\li 	\Return $(s[i,j],u1,r1,\ell)$; \End
\li \If $s[i-1,j]$ is null \Do\
\li 	$(s[i-1,j],u1,r1,\ell) \gets STR(u,r,u1,r1,\ell,\rho,i-1,j)$; \End
\li \If $s[i,j-1]$ is null \Do\
\li 	$(s[i,j-1],u1,r1,\ell) \gets STR(u,r,u1,r1,\ell,\rho,i,j-1)$; \End
\li \If $s[i-1,j-1]$ is null \Do\
\li 	$(s[i-1,j-1],u1,r1,\ell) \gets STR(u,r,u1,r1,\ell,\rho,i-1,j-1)$;\End
\li $s[i,j] \gets \min\{(s[i-1,j]+\rho[u[i],$-$])$,\\
	$(s[i,j-1]+\rho[$-$,r[j]]),(s[i-1,j-1]+\rho[u[i],r[j]])\}$;
\li $\ell = \ell + 1$;
\li \If $s[i,j] == s[i-1,j]+\rho[u[i],$-$]$ \Do 
\li 	$u1[\ell] = u[i]$;
\li 	$r1[\ell] =$ -; \End
\li \If $s[i,j] == s[i,j-1]+\rho[$-$,r[j]]$ \Do 
\li 	$u1[\ell] =$ -;
\li 	$r1[\ell] = r[j]$; \End
\li \If $s[i,j] == s[i-1,j-1]+\rho[u[i],r[j]]$ \Do 
\li 	$u1[\ell] = u[i]$;
\li 	$r1[\ell] = r[j]$; \End
\li \Return $(s[i,j],u1,r1,\ell)$;
\end{codebox}
\caption{Search Term Replacement algorithm}
\end{algorithm}

Let $s[i,j]$ be the minimum difference of two prefixes $u[1..i]$ and $r[1..j]$, where $0 \leq i \leq m$ and $0 \leq j \leq n$. The recursive formula for computing $s[i,j]$ is : 
\[s[i,j] = \min\{s[i-1,j]+\rho[u[i],-],s[i,j-1]+\rho[-,r[j]],s[i-1,j-1]+\rho[u[i],r[j]]\} \]

Next we justify why dynamic programming is applicable for this problem. First, let's see that the problem presents an optimal substructure. Given two terms $u = (u_1,...,u_n)$ and $v = (v_1,...,v_m)$ (two strings over an alphabet of size $a$), the difference between these is defined as the minimum number of changes required to go from one term (user's search term) to the other (replacement term). To obtain the replacement term, we start with the user's search term and we can either: copy or replace a letter in the user's term to match a letter in the same position in the replacement term or skip one letter in one of the two terms. We have thus three cases.
Let $c = (c_1,...,c_p)$ be the cheapest sequence of changes to go from $u$ to $v$.
\begin{itemize}
	\item Let $u' = (u_1,...,u_{n-1})$, $v' = (u_1,...,u_{m-1})$ and $c' = (c_1,...,c_{p-1})$. Suppose that $c_p$ is a copy or replace change to go from $u$ to $v$. We claim that $c'$ is the cheapest sequence of changes to go from $u'$ to $v'$. Suppose now that $d = (d_1,...,d_q)$ is cheaper than $c'$ and also gives $v'$ from $u'$, then $d = (d_1,...,d_q,c_p)$ is cheaper than $c$ and also gives $v$ from $u$ which is a contradiction.
	\item Let $v' = (v_1,...,v_{n-1})$ and $c' = (c_1,...,c_{p-1})$. Suppose that $c_p$ is an skip operation on the user's term to go from $u$ to $v$. We claim that $c'$ is the cheapest sequence of changes to go from $u' = u$ to $v'$. Suppose now that $d = (d_1,...,d_q)$ is cheaper than $c'$ and also gives $v'$ from $u'$, then $d = (d_1,...,d_q,c_p)$ is cheaper than $c$ and also gives $v$ from $u$ which is a contradiction.
	\item Let $u' = (u_1,...,u_{n-1})$ and $c' = (c_1,...,c_{p-1})$. Suppose that $c_p$ is an skip operation on the replacement term needed to get $v$ from $u$. We claim that $c'$ is the cheapest sequence of changes to go from $u'$ to $v' = v$. Suppose now that $d = (d_1,...,d_q)$ is cheaper than $c'$ and also gives $v'$ from $u'$, then $d = (d_1,...,d_q,c_p)$ is cheaper than $c$ and also gives $v$ from $u$ which is a contradiction.
\end{itemize}
Based on this proofs it's clear that problem of computing the minimum difference can be divided into a 'small' number of distinct subproblems such that the solution of the problem is easily computed using the solutions of the smaller ones.

Now, the fact that subproblems overlap is a direct consequence of the recursive formula given above:
\begin{itemize}
	\item To compute $s[i,j]$ we need to compute $s[i-1,j]$, $s[i,j-1]$ and $s[i-1,j-1]$. 
	\item To compute $s[i-1,j]$ we need to compute $s[i-2,j]$, $s[i-1,j-1]$ and $s[i-2,j-1]$. 
	\item To compute $s[i-1,j-1]$ we need to compute $s[i-1,j-1]$, $s[i,j-2]$ and $s[i-1,j-2]$. 
\end{itemize}
It is clear, for example, that to compute $s[i,j]$ we need to compute $s[i-1,j-1]$ three times! Memoization is used to deal with the overlapping subproblems.

We can therefore conclude that dynamic programming is applicable to the problem of computing the minimum difference. Please refer to pseudo-code in algorithm~1.

Concerning the problem of returning a positioning for that minimum difference, we only need to record the positioning of two terms based on the previous problem. The core algorithm is almost the same, therefore dynamic programming is applicable to this problem too. Please refer to pseudo-code in algorithm~2. 

%~(\ref{algo:bpp1}) and ~(\ref{algo:bpp2}) 
    
\subsection{Analysis}
We compute $s[i,j]$ using the memoization approach to dynamic programming. Since the bases cases are when $i==0$ or $j==0$, we need to solve only at most $m \cdot n$ different subproblems which correspond to the elements of the matrix $s[1..m,1..n]$. We only need $\Theta(1)$ running time to compute each element of this matrix, and therefore the time complexity is $O(m \cdot n)$. \\


\section{Ring Detection in Graphs}
\label{sect:RDIG}

Recall that a \emph{path} of length $k$ from a vertex $u$ to a vertex $u'$ in a graph $G=(V,E)$ is a sequence $<v_0,v_1,...,v_k>$ of vertices such that $u = v_0$ and $u' = v_k$ and $(v_{i-1},v_i) \in E$ for $i = 1,...,k$. The \emph{length} of the path is the number of edges in that path. A path is \emph{simple} if all vertices in the path are distinct.

In an undirected graph, a path $<v_0,v_1,...,v_k>$ forms a \emph{cycle} if $k \geq 3$ and $v_0 = v_k$; the cycle is \emph{simple} if $v_0,v_1,...,v_k$ are distinct. The ring detection in graphs problem is in this sense equivalent to detect the presence of a simple cycle in an undirected graph. We \emph{cannot} assume that the graph is connected. An undirected graph is \emph{connected} if every vertex is reachable from all other vertices.

There is a very useful theorem in the textbook of the course:
\begin{quotation}
\noindent (\emph{Theorem 22.10}) In a depth-first search of an undirected graph $G$, every edge of $G$ is either a tree edge or a back edge. 
\end{quotation}
\emph{Tree edges} are edges in the depth-first forest produced by a depth-first search.
The strategy to solve this problem is to use the fact that the Depth First Search (DFS) algorithm has enough information to classify some edges as it encounters them. In particular, we can find \emph{black edges} which are those connecting a vertex $u$ to an ancestor $v$ in a depth-first tree. 

\subsection{Algorithm}

We take the DFS algorithm given in the textbook and take advantage that it colors the vertices during the search to to indicate their state. Every vertex:
\begin{itemize}
	\item is initially WHITE
	\item is GRAYed when is discovered by the search
	\item is BLACKened when its adjacency list has been examined completely	
\end{itemize}
furthermore:
\begin{quotation}
\noindent ``The gray vertices always form a linear chain of descendants corresponding to the stack of active $\proc{DFS-VISIT}$ invocations; the number of gray vertices is one more than the depth in the depth-first forest of the vertex most recently discovered. Exploration always proceeds from the deepest gray vertex, so an edge that reaches another gray vertex has reached an ancestor.''
\end{quotation}

In summary, to solve this problem we modify the original DFS algorithm to detect if when first exploring an edge $(u,v)$, the color of the vertex $v$ is GRAY and therefore the edge is a back edge. Please, refer to the pseudo-code in algorithm~3 and algorithm~4.

\begin{algorithm} % make it float to the top of a page
\begin{codebox}
\Procname{$\proc{Contains-Cycle}(G)$}
\Signature{$Graph \to boolean$}
\Pre{$G$ is an undirected graphs with vertices $G.V$ and edges $G.E$}
\Post{The return value is $true$ if there is a cycle in $G$ and is $false$ otherwise} \\
\Variant {All loops iterate through a finite set of elements}
\li \For each vertex $u \in G.V$ \Do 
\li 	$u.color$ = WHITE \End
\li \For each vertex $u \in G.V$ \Do
\li 	\If $u.color$ == WHITE \Do
\li 		\If $\proc{Find-Back-Edge}(G,u)$ \Do
\li 			\Return true \End \End \End
\li \Return false
\end{codebox}
\caption{Ring Detection in Graphs}
\label{algo:RDIG1}
\end{algorithm}

\begin{algorithm} % make it float to the top of a page
\begin{codebox}
\Procname{$\proc{Find-Back-Edge}(G,u)$}
\Signature{$(Graph, Vertex) \to boolean$}
\Pre{$G$ is an undirected graphs with vertices $G.V$ and edges $G.E$} \\
\quad and $u \in G.V$
\Post{The return value is $true$ if there exists a back edge in the depth-fist-tree} \\
\quad with root $u$ and is $false$ otherwise \\
\Variant {All loops iterate through a finite set of elements}
\li $u.color$ = GRAY 
\li \For each vertex $v \in G.Adj[u]$ \Do 
\li 	\If $v.color$ == GRAY \Do 
\li 		\Return true \End
\li 	\If $v.color$ == WHITE \Do 
\li 		\If $\proc{Find-Back-Edge}(G,v)$ \Do
\li 			\Return true \End \End \End
\li $u.color$ = BLACK 
\li \Return false
\end{codebox}
\caption{Ring Detection in Graphs (cont.)}
\label{algo:RDIG2}
\end{algorithm}

\subsection{Analysis}
The running time of DFS is $\Theta(|V|+|E|)$. We can take advantage of the fact that we are working on an undirected graph. Recall that in a depth-first search of an undirected graph $G$, every edge of $G$ is either a tree edge or a back edge. Observe that if there are only tree edges, we can build each three of the forest as follows: start with the root vertex, if we want to add an edge we \emph{have to} add a new vertex. Therefore $|V| \geq |E| + 1$. Thus if we visit a number of \emph{edges} equal to $|V|$ means that we have visited a back edge. As the worst case of our algorithm happens when there is a back edge (for example, when just a line connecting all the vertices and one cycle in the end), the running time of our algorithm is therefore $O(|V|)$.
%The running time of DFS is $\Theta(|V|+|E|)$.\\ 
%We can take advantage of the fact that we are working on an undirected graph. Suppose that we are constructing the depth-first-tree from a root vertex (see the algorithm for $\proc{Find-Back-Edge}$ in algorithm~3). To put a new vertex in the this tree, we also need to put a new edge. This gives the clue that $|V| = |E| + 1$ might hold. Recall that in a depth-first search of an undirected graph $G$, every edge of $G$ is either a tree edge or a back edge.\\
%In the first case if there are only tree edges,which means there is not any circle in $G$ then $|V| = |E| + 1$, and then we can get:\\
% $\Theta(|V|+|E|)=\Theta(|V|+|V|-1)=\Theta(2 \cdot |V|-1)=\Theta(|V|)$.\\
%In the other case if there are also some back edges, assume there are $n$ circles in $G$,we can get $|E|=|V|+n-1$.The worst case of our algorithm using DFS is to go through $|V|$ edges.
%With $n$ circles in $G$,the largest depth is $|V|-2*n$ for our algorithm to be the worst case,where each circles has only $3$ edges.In the worst case,we'll go through to the deepest depth and then one circle,the running time is\\
% $O(||V|-2*n+(3-1)|)=O(|V|-2*n+2) \leq O(|V|-2 \cdot +2)=O(|V|)$\\
%%The running time of other cases is less than this one, because if there are more circles the depth will be less and we will only go through one circle.And in this case, $|E|=|V|$ the running time is $O(|V|+|E|)=O(2 \cdot |V|)=O(|V|)$.\\
%In conclusion,the running time of our algorithm is $O(|V|)$.
%%this undirected graph $|V| > |E| + 1$.
%%
%%Therefore the inequality $|V| \geq |E| + 1$ will hold, and we can safely state that the running time is $O(|V|)$.

\section{Recomputing the MST}
\label{sect:RMST}
Recall that a \emph{minimum spanning tree} (MST) is defined on an undirected graph $G = (V,E)$ with a weight function $w: E \to R$. The algorithms we studied to compute the MST grow it one edge at a time managing a set of edges $A$ using the following loop invariant: prior to each iteration, $A$ is a subset of some minimum spanning tree. At each step we determine an edge $e$ that we can add to $A$ without violating this invariant, in this sense $A \cup {e}$ is also a subset of a minimum spanning tree. We call such an edge a \emph{safe edge} for $A$.

A \emph{cut} $(S, S - V)$ of an undirected graph $G = (V,E)$ is a partition of $V$. We say that an edge $(u,v) \in E$ crosses the cut $(S, S - V)$ if one of its endpoints is in $S$ and the other is in $V - S$. We say that a cut \emph{respects} a set $A$ of edges if no edge in $A$ crosses the cut. An edge is a \emph{light edge} crossing a cut if its weight is the minimum of any edge crossing the cut. 

The key idea to solve this problem is to notice that when deleting an edge from a MST we produce a cut, and with this cut and a (probably new) safe edge we can build a new MST. There are two very useful theorems in the textbook of the course that help to see this fact:
\begin{quotation}
\noindent (\emph{Theorem 23.1}) Let $G=(V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, let $(S, V - S)$ be any cut that respects $A$, and let $(u,v)$ be a light edge crossing $(S, S-V)$. Then, edge $(u,v)$ is safe for $A$. 
\end{quotation}
\begin{quotation}
\noindent (\emph{Corollary 23.2}) Let $G=(V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, and let $C=(V_C,E_C)$ be a connected component (tree) in the forest $G_A = (V,A)$. If $(u,v)$ is a light edge connecting $C$ to some other component in $G_A$, then $(u,v)$ is safe for $A$.
\end{quotation}

\subsection{Algorithm}
We are given a graph $G=(V,E)$ with non-negative edge weights, and a minimum spanning tree (MST) $T = (V,E')$ with respect to these weights. A particular edge is modified from $w_e$ to $\hat{w}_e$. There are four cases:
\begin{itemize}
	\item $e \notin E'$ and $\hat{w}_e > w_e$
	\item $e \notin E'$ and $\hat{w}_e < w_e$
	\item $e \in E'$ and $\hat{w}_e > w_e$
	\item $e \in E'$ and $\hat{w}_e < w_e$
\end{itemize}

Let's consider first the trivial cases. 
\begin{itemize}
	\item When $e \in E'$ and $\hat{w}_e < w_e$, i.e. when we decrease the weight of an edge in the MST. Nothing happens, $T$ remains unchanged because $e$ remains as the light edge crossing the cut given by removing $e$ from $T$.
	\item Similarly, when $e \notin E'$ and $\hat{w}_e > w_e$, i.e. when we increase the weight of an edge which is not part of the MST. Nothing happens, $T$ remains unchanged because all the light edges chosen when building the MST remain the same.
\end{itemize}

Now let's consider the non-trivial cases. 
\begin{itemize}
	\item When $e \in E'$ and $\hat{w}_e > w_e$, i.e. when we increase the weight of an edge in the MST. Could be the case that $e$ with its new weight is no longer the light edge crossing the cut given by removing $e$ from $T$. Therefore we should, again, find the edge with the minimum weight that crosses this cut, and if it is different from $e$ we use it to replace $e$.
	\item When $e \notin E'$ and $\hat{w}_e < w_e$, i.e. when we decrease the weight of an edge that is not in the MST. Could be the case that $e = (a,b) $ with its new weight is lighter than some previously computed light edges. Therefore we should consider all possible cuts where the two parts contain either $a$ or $b$, and compare the weight of $e$ wit all the edges that cross these cuts. After comparing, in the case we find some light edges that are heavier than $e$, we take the \emph{largest} of these edges and replace it with $e$. 
\end{itemize}

Please, refer to algorithm~5,algorithm~6 and algorithm~7 to see the proposed pseudo-code for the case when $e \in E'$ and $\hat{w}_e > w_e$.

\begin{algorithm} % make it float to the top of a page
\begin{codebox}
\Procname{$\proc{Mark-DFS}(G, u)$}
\Signature{$(Graph, Vertex) \to Graph$}
\Pre{$G$ is an undirected graphs with vertices $G.V$ and edges $G.E$.} \\
\quad All edges $G.E$ are marked with color = WHITE 
\Post{The return value is $G$ with the nodes reachable from $u$ in a DFS } \\
\quad marked with color = BLUE \\
\Variant {All loops iterate through a finite set of elements}
\li $u.color$ = GRAY
\li \For each vertex $v \in G.adj[u]$ \Do 
\li		\If $v.color$ = WHITE \Do
\li 		$\proc{Mark-DFS}(G,v)$ \End \End
\li $u.color$ = BLUE
\end{codebox}
\caption{Recomputing the MST}
\label{algo:RMST}
\end{algorithm}

\begin{algorithm} % make it float to the top of a page
\begin{codebox}
\Procname{$\proc{Update-MST}(G, T, w, e)$}
\Signature{$(Graph, MST, Weight\_fn, Edge) \to MST$}
\Pre{$G$ is an undirected graphs with vertices $G.V$ and} \\
\quad non-negative edges $G.E$. $T$ is a minimum spanning tree with respect \\
\quad to these edges. $e$ is an edge $(e.x, e.y)$ in T. \\
\quad The weight of $e$ has been increased but $T$ has not been updated. \\
\quad $w$ is a function that gives the weight for an edge in $G.E$
\Post{The return value is $T$ updated } \\
\Variant {All loops iterate through a finite set of elements}
\li $T.E$ = $T.E - \{e\}$
\li \For each vertex $v \in T.V$ \Do
\li 	$v.color$ = WHITE \End
\li $\proc{Mark-DFS}(T,e.x)$
\end{codebox}
\caption{Recomputing the MST (cont.)}
\label{algo:RMST}
\end{algorithm}

\begin{algorithm} % make it float to the top of a page
\begin{codebox}
\li $minWeight = w(e)$
\li $minWeightEdge = e$
\li \For each vertex $u \in T.V$ \Do
\li 	\If $u.color$ == BLUE \Do 
\li 		\For each vertex $v \in G.Adj[u]$ \Do 
\li 			\If $v.color$ != BLUE \mbox{ and } $w(u,v) < minWeight $ \Do 
\li 				$minWeight = w(u,v)$
\li 				$minWeightEdge = (u,v)$ \End \End \End \End
\li $T.E$ = $T.E \cup \{minWeightEdge\}$
\end{codebox}
\caption{Recomputing the MST (cont.)}
\label{algo:RMST}
\end{algorithm}

\subsection{Analysis}
The running time of the DFS function Mark-DFS is $\Theta(|V|+|E|)$. The running time for the loop of vertices in MST is $\Theta(|V|)$. The running time for for the loop of vertices in $G.Adj[u]$, since $\displaystyle\sum_{v \in V} G.Adj[u] = |E|$, is $\Theta(|E|)$. The running time in total is thus $\Theta(|V|+|E|)+\Theta(|V|)+\Theta(|E|)=\Theta(|V|+|E|)$, which is linear of $G$ as required.

\section*{Declarations}
\begin{itemize}
	\item The material in this report is solely produced by its authors, except where otherwise indicated and clearly referenced.
	\item All definitions presented when describing the problems were taken from the book ``Introduction to algorithms'' third edition by Cormen, Leiserson, Rivest and Stein.
\end{itemize}

\end{document}
